package com.lin.codesnippet.sort;

import com.lin.enums.codesnippet.SortStatusCode;
import com.lin.codesnippet.sort.util.SortUtil;

/**
 * 归并排序
 * <p>O(nlogn)~O(nlogn)~O(nlogn)</p>
 * 稳定
 *
 * @author linqiankun
 */
public class MergeSort {


    /**
     * 非递归归并排序(错误)
     *
     * @param array          需要排序的数组
     * @param sortStatusCode 排序方式
     */
    public static void mergeSortedIteration(int[] array, SortStatusCode sortStatusCode) {
        int left, mid, right;
        for (int i = 1; i < array.length; i *= 2) {
            left = 0;
            while (left + i < array.length) {
                mid = left + i - 1;
                right = mid + 1 < array.length ? mid + 1 : array.length - 1;
                merge(array, sortStatusCode, left, mid, right);
                left = mid + 1;
            }
        }
    }


    /**
     * 递归使用归并排序
     *
     * @param array          需要排序的数组
     * @param sortStatusCode 排序方式
     * @param left           左边界
     * @param right          右边界
     */
    public static void mergeSortedRecursion(int[] array, SortStatusCode sortStatusCode, int left, int right) {
        if (left == right) {
            return;
        }
        int mid = (left + right) / 2;
        //前半段数组归并
        mergeSortedRecursion(array, sortStatusCode, left, mid);
        //后半段数组归并
        mergeSortedRecursion(array, sortStatusCode, mid + 1, right);
        //归并合并
        merge(array, sortStatusCode, left, mid, right);
    }

    /**
     * 数组合并
     *
     * @param array          需要合并的数组
     * @param sortStatusCode 排序方式
     * @param left           左边界
     * @param mid            中间位置
     * @param right          有边界
     */
    private static void merge(int[] array, SortStatusCode sortStatusCode, int left, int mid, int right) {
        int len = right - left + 1;
        int[] temp = new int[len];
        int index = 0;
        //前半段数组起始
        int i = left;
        //后半段数组起始
        int j = mid + 1;
        //两组数据归并操作
        while (i <= mid && j <= right) {
            temp[index++] = sortStatusCode.getCode() == SortUtil.compare(array[i], array[j]) ? array[i++] : array[j++];
        }
        //上面的循环无法将两个子数组的数据全部循环到
        while (i <= mid) {
            temp[index++] = array[i++];
        }
        while (j <= right) {
            temp[index++] = array[j++];
        }
        //数据放入原
        int tindex = 0;
        while (tindex < temp.length) {
            array[left++] = temp[tindex++];
        }

    }
}
